/* 
 * File:   double_list.h
 * Author: james
 *
 * Created on 2011年4月21日, 下午7:28
 */

#ifndef DOUBLE_LIST_H
#define	DOUBLE_LIST_H

namespace edm
{
    namespace common
    {
//!  description:  the double linked list node
//!  thread safe:  unsafe
//!  Usage:     double_list_node_t<data_type> node();
//!             double_list_node_t<data_type> node(data);
template<typename data_type>
struct double_list_node_t
{
  typedef struct double_list_node_t<data_type> node_type;

  double_list_node_t() : front(NULL), next(NULL), data()
  {
    // Empty
  }

  double_list_node_t(const data_type& in_data) : front(NULL), next(NULL), data(in_data)
  {
    // Empty
  }

  node_type* front;
  node_type* next;
  data_type data;
};

//!  description:   the double linked list object
//!                 this list just operate the list node directly
//!                 donot manager node memory allocate and free
//!  thread safe:  unsafe
//!  Usage:     double_list_t<data_type> double_list();
//!             double_list.push_back(data_type*);
//!             double_list.erase(data_type*);
template<typename data_type>
class double_list_t
{
public:
  //! defines the node type
  typedef double_list_node_t<data_type> node_type;

public:
  //!  double_list_t: constructor
  double_list_t();

  //!  ~double_list_t: destructor which donot free node memory
  ~double_list_t();

  //!  push_front: push the node onto the header of list
  //!  @in   node_type*: the pointer of new node
  //!  @result: int 0: success, -1: new node is NULL pointer
  int push_front(node_type* node);

  //!  push_back: push the node onto the tail of list
  //!  @in   node_type*: the pointer of new node
  //!  @result: int 0: success, -1: new node is NULL pointer
  int push_back(node_type* node);

  //!  pop_front: pop out the header node of list
  //!  @result: node_type*: the pointer of pop node, NULL: list is empty
  node_type* pop_front();

  //!  pop_back: pop out the tail node of list
  //!  @result: node_type*: the pointer of pop node, NULL: list is empty
  node_type* pop_back();

  //!  begin: gets the first header node pointer
  //!  @result: node_type*: the pointer of node, NULL: list is empty
  node_type* front();

  //!  begin: gets the last tail node pointer
  //!  @result: node_type*: the pointer of node, NULL: list is empty
  node_type* back();

  //!  erase: erase the special node from list
  //!  @in   node_type*: the pointer of new node
  //!  @result: int 0: found and erase it, -1: donot find special node
  int erase(node_type* node);

  //!  empty: identify whether list  has element
  //!  @result: bool
  bool empty();

private:
  //! the header pointer of double linked list
  node_type* m_header;

  //! the tail pointer of double linked list
  node_type* m_tail;
};

template<typename data_type>
double_list_t<data_type>::double_list_t() : m_header(NULL), m_tail(NULL)
{
  // Empty
}

template<typename data_type>
double_list_t<data_type>::~double_list_t()
{
  //! this object donot free the node memory
  m_header = NULL;
  m_tail = NULL;
}

template<typename data_type>
int double_list_t<data_type>::push_front(node_type* node)
{
  if (!node)
  {
    return -1;
  }

  node->front = NULL;
  node->next = NULL;
  if (!m_header)  //! list is empty
  {
    m_header = node;
    m_tail = node;
  }
  else
  {
    node->next = m_header;
    m_header->front = node;
    m_header = node;
  }

  return 0;
}

template<typename data_type>
int double_list_t<data_type>::push_back(node_type* node)
{
  if (!node)
  {
    return -1;
  }

  node->front = NULL;
  node->next = NULL;
  if (!m_tail)  //! list is empty
  {
    m_header = node;
    m_tail = node;
  }
  else
  {
    m_tail->next = node;
    node->front = m_tail;
    m_tail = node;
  }

  return 0;
}

template<typename data_type>
double_list_node_t<data_type>* double_list_t<data_type>::pop_front()
{
  node_type* ret = NULL;

  if (!m_header)
  {
    ret = NULL;
  }
  else if (m_header == m_tail)
  {
    ret = m_header;
    m_header = NULL;
    m_tail = NULL;
  }
  else
  {
    ret = m_header;
    m_header = m_header->next;
    ret->next = NULL;
    m_header->front = NULL;
  }

  return ret;
}

template<typename data_type>
double_list_node_t<data_type>* double_list_t<data_type>::pop_back()
{
  node_type* ret = NULL;

  if (!m_tail)
  {
    ret = NULL;
  }
  else if (m_header == m_tail)
  {
    ret = m_tail;
    m_header = NULL;
    m_tail = NULL;
  }
  else
  {
    ret = m_tail;
    m_tail = m_tail->front;
    ret->front = NULL;
    m_tail->next = NULL;
  }

  return ret;
}

template<typename data_type>
double_list_node_t<data_type>* double_list_t<data_type>::front()
{
  return m_header;
}

template<typename data_type>
double_list_node_t<data_type>* double_list_t<data_type>::back()
{
  return m_tail;
}

template<typename data_type>
int double_list_t<data_type>::erase(node_type* node)
{
  if (!node ||  !m_header)
  {
    return -1;
  }

  int ret = -1;
  if (!(node->front) && !(node->next))
  {
    if (m_header == m_tail && m_header == node)
    {
      m_header = NULL;
      m_tail = NULL;
      ret = 0;
    }
  }
  else if (!(node->front) && node->next)
  {
    if (m_header == node)
    {
      m_header = m_header->next;
      m_header->front = NULL;
      node->next = NULL;
      ret = 0;
    }
  }
  if (node->front && !(node->next))
  {
    if (m_tail == node)
    {
      m_tail = m_tail->front;
      m_tail->next = NULL;
      node->front = NULL;
      ret = 0;
    }
  }
  else if (node->front && node->next)
  {
    node_type* node_front = node->front;
    node_type* node_next = node->next;
    node->front = NULL;
    node->next = NULL;
    node_front->next = node_next;
    node_next->front = node_front;
    ret = 0;
  }

  return ret;
}

template<typename data_type>
bool double_list_t<data_type>::empty()
{
  return !m_header;
}
    
    
    }
}


#endif	/* DOUBLE_LIST_H */

